The present invention is directed to the generation of tests for complex digital circuitry. It has particular application to tests for non-scan-type circuits.
As the complexity of circuits provided on a single semiconductor chip has increased, the difficulty of determining whether a particular chip is functional has increased geometrically. As the complexity increases, the number of states of the chip increases rapidly. For many chips, the time required to test every state for every possible input to the chip, even if a change of inputs could be made every picosecond, would be greater than the 18 billion years since the Big Bang.
For most circuits that are actually manufactured, however, it is possible to test for all likely defects by means of tests that can be performed in a reasonable amount of time, but the design of such tests has itself proved quite complex. Because of the complexity of such tests, it has been necessary to design them by machine; manual generation of the tests has proved impractical for the more complex circuits. It is to methods for designing such tests that the present invention is directed.
At this point, it is beneficial to set forth the nomenclature that will be employed throughout the rest of the specification; nomenclature in this area is often confusing because identical terms often have different meanings at different times.
In some very simple digital circuits, such as NAND gates, the output of the circuit is determined entirely by its input; the circuit has no memory. However, if the circuit is given some feedback, it can be made into a memory element, such as a flip-flop. In a D-type flip-flop, the output, which represents its current state, is determined not by the current input but rather by the input at the most recent clock time. In a J-K-type flip-flop, the output is determined not only by the input at the most recent clock time but also by the previous state of the flip-flop.
In both of these types of flip-flops, and in flip-flops generally, the state of the individual flip-flop can have one of two values. If the flip-flop is part of a larger circuit, the value of its individual state can be considered a state variable comprising one of the components of a vector representing the state of the entire circuit. In order to differentiate between the state of the entire circuit and the sttes of individual components, the term state will hereinafter be used to indicate the value of the vector consisting of all the state variables representing the components making up the circuit.
The terms input and output will be used to describe signals on individual physical terminals or ports, e.g., input pins on the chip to be tested, and output will be used to represent signals on individual output ports. The term input vector will be used to describe the ensemble of input signals on the input ports, while the term output vector will be used to describe the ensemble of signals on the output ports.
A fault or fault origin is the physical defect in a faulty circuit. A fault effect is a difference caused by a fault between a signal in a faulty version of a circuit and the signal at the same position in the fault-free version of the same circuit after any particular sequence of inputs to the circuit.
In order to determine that a fault is present in a circuit, a sequence of input vectors must be selected that will cause the fault to result in a difference between the outputs of the faulty version and the outputs of a fault-free version. For example, if a defect in a faulty version is a signal line that is stuck at a zero value, and if that signal line is an input to an AND gate whose output is a circuit output, then it is necessary, in order to detect the fault, to provide signals that would cause ones to appear at both input ports of the AND gate if the circuit were not faulty. Any other set of signals would result in an output of the AND gate in the faulty version that is the same as the AND-gate output in the fault-free version, so there would be no basis from which it could be inferred that the faulty version is faulty.
A fault origin can be so deeply imbedded in a circuit that it is impossible for the fault effects resulting from a fault origin to propagate to an output without the application of a very long sequence of inputs. That is, although the fault origin can often be made to cause a difference between the state of the faulty version and that of the fault-free version by application of a single input vector, the state variable or variables in which the two versions differ may not be immediately observable in the circuit output.
In the past, this has caused some difficulty in designing tests for circuits of high complexity. Many such circuits have therefore been designed to include additional circuitry that allows the state components of the circuit to be connected as a shift register so that the state variables can easily be read directly. The same circuitry allows the state of the circuit to be set directly. For instance, one pin in a multi-pin circuit could indicate whether the circuit is to operate in the normal manner or as a shift register, another pin could receive the clock signal, a third pin could receive data to be written into the shift register, and a fourth pin could be a shift-register output pin, whose signal level at successive clock times would represent the contents of individual state components of the circuit viewed as a finite-state machine.
This so-called scan type of organization is beneficial because it allows tests to be designed as readily as if there were no stored state. Test-generation routines exist for finding an initial state and an input vector that will cause effects from particular faults to be propagated into a state of the machine. It is then a simple matter to read out the machine's state and observe whether there are any differences between that state and the state of a fault-free machine. The routine simply selects from among the several possible faults in the machine, employs a standard rule-of-thumb type of routine for finding a likely initial state and input vector, and then runs the chosen state and input vector through a simulator to determine that a fault effect indeed shows up in one or more of the state components of the machine.
Although this type of circuit design results in enhanced testability, it also places unwanted constraints on the circuit designer and adds complexity to the design. For instance, a memory cell in an MOS circuit might inherently require only a transmission gate followed by an inverter in order to provide the data-storage function. In order to enable the state of that memory cell to permit its state to be read as the contents of a stage in a shift register, however, the same memory cell might require a dozen gates. Thus, although the provision of scan-type circuits permits tests to be generated readily in many cases, such circuits are often needlessly complex.
If the scan-type design philosophy is not followed, on the other hand, the test-generation process can be quite difficult since it is not easy to observe the state of the device under test directly, and the determination of whether the device is faulty must be made by observing the outputs of the system only. The typical methods for developing tests for such systems involve selecting a fault origin to be detected and then employing a routine for "guessing," based on the circuit layout, at a likely sequence of input vectors that will cause effects of the fault to be propagated to the output ports of the device under test. Once a successful sequence of input vectors is found for a given fault origin, another fault origin is chosen, and the steps are repeated. This process continues until a total sequence is found that is a test for all of the faults.
A problem with this type of test-generation method is that it requires searches through many long sequences of input vectors. Since the number of possible sequences increases exponentially with the number of vectors in a sequence, such a process can be very time-consuming.
An object of the present invention is to generate tests for digital circuits without requiring that they be scan-type circuits and without using the long search routines that have been needed in the past to test circuits that are not of the scan type.